/*
题目描述：二维数组的查找
左 -> 右 升序
上 -> 下 升序
输入一个数判断是否存在该数
方法：
1. 画矩形，选取的数和target比较，分三种情况：
    相等：返回
    小于：下边或者右边
    大于：上边或者左边
2. 选取右上角（或者左下角）和target比较，然后缩减规模，分三种情况：
    相等：返回
    小于：剔除所在行
    大于：剔除列
 */
public class E4 {
    public static void main(String[] args){
        int[][] matrix = {
                {1,2,8,9},
                {2,4,9,12},
                {4,7,10,13},
                {6,8,11,15}
        };

        int target1 = 7;
        int target2 = 5;
        boolean res1 = Find(matrix, 4, 4, target1);
        boolean res2 = Find(matrix, 4, 4, target2);
        System.out.println("res1 = " + res1);
        System.out.println("res2 = " + res2);
    }
    //方法2
    private static boolean Find(int[][] matrix, int rows, int columns, int target){
        boolean found = false;

        if(matrix != null && rows > 0 && columns > 0){
            int row = 0;
            int column = columns - 1;
            while(row < rows && column >= 0){
                if(matrix[row][column] == target){
                    found = true;
                    break;
                }
                else if(matrix[row][column] > target){
                    column--;
                }
                else{
                    row++;
                }
            }
        }
        return found;
    }
}
/*
res1 = true
res2 = false
 */
